//package work.rightAnswer;
//
//class bag01_416 {
//    public boolean canPartition(int[] nums) {
//        int sum = 0;
//        for (int i = 0; i < nums.length; i++) {
//            sum+=nums[i];
//        }
//        if(sum%2==1){
//            return false;
//        }
//
//        int[][] dp = new int[nums.length][sum/2+1];
//
//        for (int i = nums[0]; i <= sum/2; i++) {
//            dp[0][i] = nums[0];
//        }
//
//        for (int i = 1; i < nums.length ; i++) {
//            for (int j = 0; j <= sum/2; j++) {
//                if(j<nums[i]){
//                    dp[i][j] = dp[i-1][j];
//                }else {
//                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
//                }
//            }
//        }
//
//        return dp[nums.length-1][sum/2+1]==sum/2;
//
//    }
//
//    public boolean isVaild(int[] nums,int index,int capacity){
//        if(capacity<0){
//            return false;
//        }
//        if(capacity==0){
//            return true;
//        }
//        if(index<0){
//            return false;
//        }
//        return isVaild(nums,index-1,capacity-nums[index])||isVaild(nums,index-1,capacity);
//    }
//}